package lcr;

import java.util.ArrayDeque;

public class Test0048 {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);
        TreeNode node10 = new TreeNode(10);
        node1.left = node2;
        node1.right = node3;
        node3.left = node4;
        node3.right = node5;
        node4.left = node6;
        node4.right = node7;
        node5.left = node8;
        node6.left = node9;
        node7.right = node10;
        Codec codec = new Codec();
        String serialize = codec.serialize(node1);
        TreeNode deserialize = codec.deserialize(serialize);
    }
}

class Codec {
    final char delimiter = (char) 2000;
    final char nullNode = (char) 2001;
    final char minus = (char) 2002;


    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder stringBuilder = new StringBuilder();
        dfs(root, stringBuilder);

        return stringBuilder.toString();
    }

    private void dfs(TreeNode node, StringBuilder stringBuilder) {
        if (node == null){
            stringBuilder.append(nullNode);
            return;
        }
        int val = node.val;
        if (val < 0){
            stringBuilder.append(minus);
            val = -val;
        }
        stringBuilder.append((char) val);

        if (node.left == null&& node.right==null) {
            stringBuilder.append(delimiter);
            return;
        }
        dfs(node.left, stringBuilder);
        dfs(node.right, stringBuilder);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        char[] charArray = data.toCharArray();

        TreeNode ans = new TreeNode(),pre=ans;
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.add(ans);
        boolean isNegative = false;
        for (char c : charArray) {
            switch (c){
                case delimiter:
                    deque.pollLast();
                    pre=null;
                    break;
                case nullNode:
                    if (pre==null)deque.pollLast();
                    pre=null;
                    break;
                case minus:
                    isNegative=true;
                    break;
                default:
                    int val = isNegative?-c:c;
                    TreeNode node = new TreeNode(val);
                    if (pre!=null) pre.left=node;
                    else deque.pollLast().right=node;
                    pre=node;
                    deque.add(node);
                    isNegative=false;
                    break;
            }

        }

        return ans.left;
    }
}
